//因为这个是项目的名字，所以关于这个项目的大体要求及思路就在这个文件里，剩下的关于其他类的详细内容还是在其他类里面写
//给定一个典型的英文文本文件，将其转换为一个相同字符序列多次相邻出现的文本文件。
//  Burrows–Wheeler的目标并非压缩消息，而是将其转换为更易于压缩的形式。
// 布罗斯-惠勒变换会重新排列输入中的字符，使其包含大量重复字符的簇，但仍然可以恢复原始输入。

import edu.princeton.cs.algs4.BinaryStdIn;
import edu.princeton.cs.algs4.BinaryStdOut;
import edu.princeton.cs.algs4.Merge;

import java.util.Arrays;

public class BurrowsWheeler {
    // apply Burrows-Wheeler transform,
    // reading from standard input and writing to standard output
    // 从标准输入中读取从标准输出中输出
    // 输入的时候输入原始字符串，我们需要根据原始字符串构建循环后缀数组和排序后的循环后缀数组
    // 最后输出的时候需要输出原始字符串在排序后的循环后缀数组中的位置，用四个字节表示，以及排序后循环后缀数组最后一列
    public static void transform() {
        String s = BinaryStdIn.readString();
        // String s="ABRACADABRA!";
        int original = 0;
        CircularSuffixArray suffixArray = new CircularSuffixArray(s);
        String twoS = s;
        char[] t = new char[s.length()];
        twoS += twoS;
        for (int i = 0; i < s.length(); i++) {
            t[i] = twoS.charAt(suffixArray.index(i) + s.length() - 1);
            if (suffixArray.index(i) == 0) {
                original = i;
            }
        }
        BinaryStdOut.write(original);
        for (int i = 0; i < s.length(); i++) {
            BinaryStdOut.write(t[i]);

            // Debug
            // System.out.printf("%c",t[i]);
        }
        BinaryStdOut.close();
    }

    // apply Burrows-Wheeler inverse transform,
    // reading from standard input and writing to standard output
    // 我们读取到循环后缀数组最后一列以及原始数组在循环后缀数组中的位置
    // 需要输出原始数组
    // 首先要根据最后一列构建排序后循环后缀数组的第一列，因为他们都是相同的字符，所以我们只需对最后一列进行排序就可得
    // 我们需要构建next数组，根据第一列以及first我们就可以得到第一个字符，next[first]得到第二个，next[next[first]]得到第三个，以此类推得到原始字符串
    // 关于构建next：以'c'开头的串的next串一定以'c'结尾，因此如果'c'是唯一的，那么我们只需找到这两种串，我们就知道next[以c为开头]=以c为结尾
    // 但是如果字符并不唯一，我们就需要考虑到一个原则：假如有两个以c为开头和两个以c为结尾的，那么第一个对第一个，第二个对第二个，也就是顺序不变
    public static void inverseTransform() {
        // 得到first t[] 以及firstcol[] 初始化next
        int first=BinaryStdIn.readInt();
        String t=BinaryStdIn.readString();
        char[] chars = t.toCharArray();
        charSet[] setOfChar=new charSet[t.length()];
        for(int i=0;i<t.length();i++)
        {
            setOfChar[i]=new charSet();
            setOfChar[i].key=chars[i];
            setOfChar[i].value=i;
        }
        Arrays.sort(chars);
        String firstCol=new String(chars);
        int[] next = new int[t.length()];

        Merge.sort(setOfChar);    // 从next[tmp]里得到next
        for(int i=0;i<t.length();i++)
        {
            next[i]=setOfChar[i].value;
        }

        // 用next得到原字符串，然后输出
        BinaryStdOut.write(firstCol.charAt(first));
        int tmp = first;
        for (int i = 0; i < t.length() - 1; i++) {
            BinaryStdOut.write(firstCol.charAt(next[tmp]));
            tmp = next[tmp];
        }
        BinaryStdOut.close();
    }
    // if args[0] is "-", apply Burrows-Wheeler transform
    // if args[0] is "+", apply Burrows-Wheeler inverse transform
    public static void main(String[] args) {
        if(args[0].equals("-"))
        {
            transform();
        }
        else
        {
            inverseTransform();
        }
    }
}
